package leetcode.p1833;

/**
 * @author: trtan
 * @date: 2021-07-02 15:51
 **/
public class MaximumIceCreamBars {
    /**
     * 这题可以排序，可以计数，因为最大值不是很大，采用计数的话复杂度是O(n)的
     * @param costs
     * @param coins
     * @return int
     * @author trtan
     * @date 2021/7/2 16:02
     */
    public int maxIceCream(int[] costs, int coins) {
        final int MAX_VALUE = 100000;
        int [] cnt = new int[MAX_VALUE + 5];
        for (int i = 0; i < costs.length; i++) {
            cnt[costs[i]]++;
        }
        int ans = 0;
        for (int i = 1; i <= MAX_VALUE; i++) {
            int x = cnt[i] * i;
            if (x <= coins) {
                coins -= x;
                ans += cnt[i];
            } else {
                int d = coins / i;
                coins %= i;
                ans += d;
            }
        }
        return ans;
    }
}
